package arithmetic.demo2;

import java.util.Scanner;


/**
 * 题目: 动态规划: 01 背包问题
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), maxV = in.nextInt();
        int[] height = new int[n + 1];
        int[] V = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            V[i] = in.nextInt();
            height[i] = in.nextInt();
        }

        // 创建 dp 表
        int[][] dp = new int[n + 1][maxV + 1];


        // 当 <= j  的情况
        // 进行状态转移
        for (int i = 1; i <= n ; i++) {
            // 这里的j 表示当前位置下的最大的体积
            // dp[i][j] 就表示 height[i] 位置下的  <= j 体积的最大重量
            for (int j = 1; j <= maxV; j++) {
                 // 分情况讨论, 分别得到 当前位置是否需要加入
                // 先更新当前位置不加入的情况
                dp[i][j] = dp[i - 1][j];

                // 只有当前位置还能装下就更新 dp
                if (j - V[i] >= 0) {
                    // 两种情况取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - V[i]] + height[i]);
                }
            }
        }

        System.out.println(dp[n][maxV]);


        dp = new int[n + 1][maxV + 1];


        // 初始化
        for(int j = 1 ; j <= maxV ; j++) {
            // 表示当前位置不能填
            // 只有体积没有重量
            dp[0][j] = -1;
        }



        // 当 <= j  的情况
        // 进行状态转移
        for (int i = 1; i <= n ; i++) {
            // 这里的j 表示当前位置下的最大的体积
            // dp[i][j] 就表示 height[i] 位置下的  <= j 体积的最大价值
            for (int j = 1; j <= maxV; j++) {
                // 分情况讨论, 分别得到 当前位置是否需要加入
                // 先更新当前位置不加入的情况
                dp[i][j] = dp[i - 1][j];
                // 只有当前位置还能装下就更新 dp
                if (j - V[i] >= 0 && dp[i - 1][j - V[i]]  != -1) {
                    
                    // 两种情况取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - V[i]] + height[i]);
                }
            }
        }

        System.out.println(dp[n][maxV] > 0  ? dp[n][maxV] : 0);

    }
}